#!/usr/bin/env python

def binary_search_v1(nums, start, end, target):
    '''
    功能描述：在nums数组中查找target值，如果找到返回target在数字中的下标值，否则返回-1
    '''
    if start > end:
        return -1

    mid = start + (end - start) // 2

    if nums[mid] == target:
        return mid
    elif nums[mid] > target:
        return binary_search_v1(nums, start, mid - 1, target)
    else:
        return binary_search_v1(nums, mid + 1, end, target)

def binary_search_v3(nums, target):
    '''
    功能描述：在nums数组中查找target值，如果找到返回target在数字中的下标值，否则返回-1
    '''
    p, q = 0, len(nums)

    while p < q:
        mid = p + (q - p) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            q = mid - 1
        else:
            p = mid + 1
    
    return -1
        
def binary_search_v2(nums, start, end, target):
    '''
    功能描述：在nums数组中查找target值，如果找到返回target在数字中的下标值，否则返回比target大的第一个元素的位置
    '''
    if start > end:
        return start

    mid = start + (end - start) // 2

    if nums[mid] == target:
        return mid
    elif nums[mid] > target:
        return binary_search_v2(nums, start, mid - 1, target)
    else:
        return binary_search_v2(nums, mid + 1, end, target)

def binary_search_v4(nums, target):
    '''
    功能描述：在nums数组中查找target值，如果找到返回target在数字中的下标值，否则返回比target大的第一个元素的位置
    '''
    p, q = 0, len(nums)

    while p < q:
        mid = p + (q - p) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            q = mid - 1
        else:
            p = mid + 1
    
    return p


arr = [10, 14, 19, 26, 27, 31, 33, 35, 42, 44]
index = binary_search_v1(arr, 0, len(arr) - 1, 31)
print(index)

index = binary_search_v2(arr, 0, len(arr) - 1, 32)
print(index)

index = binary_search_v2(arr, 0, len(arr) - 1, 45)
print(index)

index = binary_search_v2(arr, 0, len(arr) - 1, 9)
print(index)

index = binary_search_v3(arr, 31)
print(index)

index = binary_search_v4(arr, 31)
print(index)

index = binary_search_v4(arr, 32)
print(index)

index = binary_search_v4(arr, 45)
print(index)

index = binary_search_v4(arr, 9)
print(index)

index = binary_search_v3(arr, 9)
print(index)

index = binary_search_v3(arr, 32)
print(index)

index = binary_search_v3(arr, 45)
print(index)